from typing import List, Optional
import matplotlib.pyplot as plt
import networkx as nx

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    
    def __str__(self):
        values = []
        current = self
        while current:
            values.append(str(current.val))
            current = current.next
        return " -> ".join(values) + " -> None"
    
    def __repr__(self):
        return self.__str__()
    
    @staticmethod
    def from_array(arr: List[int]) -> Optional['ListNode']:
        if not arr:
            return None
        head = ListNode(arr[0])
        current = head
        for val in arr[1:]:
            current.next = ListNode(val)
            current = current.next
        return head

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    
    def __str__(self):
        return self._str_helper(0)
    
    def _str_helper(self, level):
        result = "  " * level + f"Node({self.val})\n"
        if self.left:
            result += self.left._str_helper(level + 1)
        if self.right:
            result += self.right._str_helper(level + 1)
        return result
    
    def __repr__(self):
        return self.__str__()
    
    @staticmethod
    def from_array(arr: List[Optional[int]]) -> Optional['TreeNode']:
        if not arr:
            return None
        root = TreeNode(arr[0])
        queue = [root]
        i = 1
        while queue and i < len(arr):
            node = queue.pop(0)
            if i < len(arr) and arr[i] is not None:
                node.left = TreeNode(arr[i])
                queue.append(node.left)
            i += 1
            if i < len(arr) and arr[i] is not None:
                node.right = TreeNode(arr[i])
                queue.append(node.right)
            i += 1
        return root
    
    def visualize(self):
        def add_nodes_edges(node, graph, x, y, level=1):
            if node:
                graph.add_node(node.val, pos=(x, y))
                if node.left:
                    graph.add_edge(node.val, node.left.val)
                    add_nodes_edges(node.left, graph, x-1/2**level, y-1, level+1)
                if node.right:
                    graph.add_edge(node.val, node.right.val)
                    add_nodes_edges(node.right, graph, x+1/2**level, y-1, level+1)
        
        G = nx.Graph()
        add_nodes_edges(self, G, 0, 0)
        pos = nx.get_node_attributes(G, 'pos')
        plt.figure(figsize=(8, 6))
        nx.draw(G, pos, with_labels=True, node_color='lightblue', 
                node_size=1000, font_size=12, font_weight='bold')
        nx.draw_networkx_labels(G, pos, font_size=12)
        plt.axis('off')
        plt.show()

def main():
    # 测试链表
    arr = [1, 2, 3, 5]
    head = ListNode.from_array(arr)
    print("链表:")
    print(head)

    # 测试树
    arr = [1, 2, None, 4, 5, 6, 7, None, None, 8]
    root = TreeNode.from_array(arr)
    print("\n树:")
    print(root)

    # 可视化树
    print("\n正在可视化树...")
    root.visualize()

if __name__ == "__main__":
    main()
